// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_HEAP_H_
#define ALGORITHM_SORT_HEAP_H_
#include <stack>

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		
		template<typename T>
		class Heap : public Base<T> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			Heap() :
				Base<T>::Base(kHeap)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~Heap()
			{

			}

			/**
			* sort
			*
			* @param T arr[]
			* @param int len
			* @return T
			*/
			virtual T* sort(T arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				//Build a large top heap
				for (int i = (len - 2) / 2; i >= 0; i--) {
					HeapArr(arr, i, len - 1);
				}
				//Heap sort
				for (int i = len - 1; i >= 1; i--) {
					//Exchange the top element of the heap with the last element
					std::swap(arr[i], arr[0]);
	// 	            T temp = arr[i];
	// 	            arr[i] = arr[0];
	// 	            arr[0] = temp;
					//Adjust the messed up heap to restore the characteristics of the heap
					HeapArr(arr, 0, i - 1);
				}
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const Heap& cbase
			* @return Heap&
			*/
			Heap& operator=(const Heap& cbase);

			/**
			* Copy Construction
			*
			* @param const Heap& cbase
			* @return
			*/
			Heap(const Heap& cbase);

		private:
			/**
			* HeapArr
			* Sink operation
			*
			* @param T arr[]
			* @param int h
			* @param int i
			* @return void
			*/

			T* HeapArr(T arr[], int parent, int n)
			{
				//Temporarily save the element to sink
				T temp = arr[parent];
				//Locate the position of the left child node
				int child = 2 * parent + 1;
				//Start sinking
				while (child <= n) {
					// If the right child node is larger than the left child, locate the right child
					if (child + 1 <= n && arr[child] < arr[child + 1])
						child++;
					// If the child node is less than or equal to the parent node, the sinking ends
					if (arr[child] <= temp) break;
					// The parent node sinks
					arr[parent] = arr[child];
					parent = child;
					child = 2 * parent + 1;
				}
				arr[parent] = temp;
				return arr;
			}

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_HEAP_H_
